//
// Created by LiuYou on 2021/8/2.
//

#include <cstdlib>
#include <cstdio>
#include <iostream>


int countRange(const int* array, int length, int start, int end) {
    if (array == nullptr) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < length; ++i) {
        if (array[i] >= start && array[i] <= end) {
            ++count;
        }
    }
    return count;
}

int getDuplication(const int* array, int length) {
    // 判断数组是否正确。
    if (array == nullptr || length <= 0) {
        return -1;
    }
    // 算法:
    int start = 1;
    int end = length - 1;
    while (end >= start) {
        // 把 1 ~ n 的数字从中间的数字 m 分为两部分。
        // 前面一半为 1 ~ m, 后面一半为 m + 1 ~ n。
        int middle = ((end - start) >> 1) + start;
        int count = countRange( array, length, start, middle );
        if (end == start) {
            if (count > 1) {
                return start;
            } else {
                break;
            }
        }
        if (count > (middle - start + 1)) {
            end = middle;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}


/*
 * 不修改数组找出重复的数字。这个难, 不理解。
 */
int main() {
    int array[8] = {2, 3, 5, 4, 3, 2, 6, 7};
    int value = getDuplication( array, 8 );
    fprintf( stdout, "dup: %d\n", value );

    std::cout << "=============================================================" << std::endl;
    std::cout << "(6 >> 1): " << (6 >> 1) << std::endl;
    std::cout << "(5 >> 1): " << (5 >> 1) << std::endl;
    std::cout << "(3 >> 1): " << (3 >> 1) << std::endl;
    std::cout << "(6 << 1): " << (6 << 1) << std::endl;
    std::cout << "=============================================================" << std::endl;
    std::cout << "(6 >> 1): " << (6 >> 1) << std::endl;
    std::cout << "(7 >> 1): " << (7 >> 1) << std::endl;
    std::cout << "(8 >> 1): " << (8 >> 1) << std::endl;
    std::cout << "(9 >> 1): " << (9 >> 1) << std::endl;
    std::cout << "=============================================================" << std::endl;


    exit( 0 );
}